﻿//https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {
        int hash1[128] = { 0 };
        int hash2[128] = { 0 };
        int n = s.size(), m = p.size();
        int left = 0, right = 0, len = 0;
        vector<int> ret;
        for (auto e : p)
        {
            hash1[e]++;
        }
        while (right < n)
        {
            //进窗口
            hash2[s[right]]++;
            if (hash2[s[right]] <= hash1[s[right]])
            {
                len++;
            }
            //判断条件
            if (right - left + 1 > m)
            {
                if (hash2[s[left]] <= hash1[s[left]])
                {
                    len--;
                }
                hash2[s[left]]--;
                left++;
            }

            //更新结果
            if (len == m)
                ret.push_back(left);

            right++;
        }

        return ret;

    }
};